package hot100;

public class Solution416 {

    public boolean canPartition(int[] nums) {
        int sum = 0;
        int max = nums[0];
        for (int i : nums) {
            sum += i;
            max = Math.max(max, i);
        }
        if (sum % 2 == 1 || max > sum / 2) {
            return false;
        }
        int target = sum / 2;
        boolean[][] dp = new boolean[nums.length][target + 1];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < target + 1; j++) {
                if (j == 0) {
                    dp[i][j] = true;
                    continue;
                }
                if (i == 0) {
                    if (j == nums[0]) {
                        dp[i][j] = true;
                    }
                    continue;
                }
                if (j >= nums[i]) {
                    dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i]];
                } else {
                    dp[i][j] = dp[i-1][j];
                }

            }
        }
        return dp[nums.length - 1][target];
    }

    public boolean canPartition1(int[] nums) {
        int sum = 0;
        int max = nums[0];
        for (int i : nums) {
            sum += i;
            max = Math.max(max, i);
        }
        if (sum % 2 == 1 || max > sum / 2) {
            return false;
        }
        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }
        return dp[target];
    }

    public static void main(String[] args) {
        Solution416 solution416 = new Solution416();
        System.out.println(solution416.canPartition(new int[]{1, 2, 3, 4, 5, 6, 7}));
    }
}
